package com.lsa.letcode.the101.symmetricTree;

import com.lsa.letcode.common.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
    	if (root == null) {
    		return true;
    	}
    	TreeIterator order1Iter = treeIter(root, Order.INORDER);
    	TreeIterator order2Iter = treeIter(root, Order.RIGHT_VAL_LEFT);
    	
    	while(order1Iter.hasNext() || order2Iter.hasNext()) {
    		if (!order1Iter.hasNext() || !order2Iter.hasNext()) {
    			return false;
    		}
    		
    		Integer n1 = order1Iter.next();
			Integer n2 = order2Iter.next();
			if (n1 != n2 || order1Iter.getLevel() != order2Iter.getLevel()) {
    			return false;
    		}
    	}
    	
        return true;
    }
    
    private final class TreeIterator implements Iterator<Integer> {
		private final Order order;
		private Deque<StackFrame> stack = new ArrayDeque<StackFrame>();
		private Integer next;
		
		public TreeIterator(TreeNode root, Order order) {
			stack.add(new StackFrame(root));
			this.order = order;
		}
		
		public int getLevel() {
			return stack.size();
		}
		private boolean isNextReady = false;
		private boolean isHasNext = false;

		@Override
		public boolean hasNext() {
			if (!isNextReady) {
				moveToNext();
				isNextReady = true;
			}
			return isHasNext;
		}

		private void moveToNext() {
			isHasNext = false;
			cycle:
			while(!stack.isEmpty()) {
				StackFrame f = stack.peek();
				if (f.root == null){
					stack.pop();
				}
				else {
					int step = f.step++;
					if (step == 0) {
						TreeNode n = order == Order.INORDER? f.root.left : f.root.right;
						stack.push(new StackFrame(n));
					}
					else if (step == 1) {
						next = f.root.val;
//						System.out.print(String.format("%s <-%s ", next, stack.size()));
						isHasNext = true;
						break cycle;
					}
					else if (step == 2) {
						TreeNode n = order == Order.INORDER? f.root.right : f.root.left;
						stack.push(new StackFrame(n));
					}
					else if (step == 3) {
						stack.pop();
					}
				}
			}
		}

		@Override
		public Integer next() {
			if (!isNextReady) {
				moveToNext();
			}
			isNextReady = false;
			return next;
		}

		@Override
		public void remove() {
		}
	}

	enum Order{
    	INORDER,
    	RIGHT_VAL_LEFT
    }
    
	TreeIterator treeIter(final TreeNode root, final Order order){
    	return new TreeIterator(root, order);
    }
    
    /**
     * INORDER :        0 - left, 1 - visit, 2 - right, 3 - return
     * RIGHT_VAL_LEFT : 0 - right, 1 - visit, 2 - left, 3 - return
     */
    class StackFrame{
		int step; 
		TreeNode root;
		StackFrame(TreeNode root) {
			this.root = root;
		}
	}
}